package com.zsrt.day20170410.am;


/**
*@author jzh
*@创建时间 2017年4月10日上午10:06:14
*类说明：
*/
public class QuickSort {
	
	public static void main(String[] args) {
		int[] arrays={1,3,5,4,8,7,5};
		System.out.println(11);
		QuickSort qs=new QuickSort();
		qs.quickSort(arrays,0,arrays.length-1);
		qs.p(arrays);
	}
	
	public int getKey(int[] a,int low,int high){
		int key=a[low];
		while(low<high){
			while(low<high&&key<=a[high]){
				high--;
			}
			a[low]=a[high];
			while(low<high&&a[low]<=key){
				low++;
			}
			a[high]=a[low];
		}
		a[low]=key;
		return low;
	}
	
	/*public int getKey(int a[],int low,int high){
		int pivot=a[low];
		while(low<high){
			while(low<high&&pivot<a[high]){
				high--;
			}
			a[low]=a[high];
			while(low<high&&a[low]<pivot){
				low++;
			}
			a[high]=a[low];
		}
		a[low]=pivot;
		return low;
	}*/
	
	/*public void quickSort(int[] a,int low,int high){
		if(low<high){
			int mid=getKey(a,low,high);
			quickSort(a,low,mid-1);
			quickSort(a,mid+1,high);
		}
	}*/
	
	public void quickSort(int a[],int low,int high){
		if(low<high){
			int middle=getKey(a,low,high);
			quickSort(a,low,middle-1);
			quickSort(a,middle+1,high);
		}
		
	}
	
	public  void p(int a[]){
		for(int aa:a){
			System.out.print("  "+aa+"  ");
		}
	}

	
}
